//032. 全数字乘积
//        如果一个 n 位数使用了 1 到 n 中每个数字且只使用了一次，我们称其为全数字。例如，
//        15234 这个五位数，是 1 到 5 全数字的。
//        7254 是一个不寻常的数，因为：39 × 186 = 7254 这个算式的乘数，被乘数和乘积组成了
//        一个 1 到 9 的全数字组合。
//        找出所有能够组合成 1 到 9 全数字的乘法算式中乘积的和。
//        提示: 有的乘积数字能够被多个乘法算式得到，所以在计算时要记得只计算它们一次。
//        答案：45228

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;

//看起来像是 搜索 加 剪枝优化 的题

//按位数分解只能有以下两种情况
//w代表位数, eg: 1w代表1位数
//1w X 4w = 4w
//2w X 3w = 4w

public class Week032 {
    //method1
    //对此进行全排列，然后按位分解，判断是否符合条件
    static final int N = 9;
    static boolean[] book = new boolean[N + 1];
    static int[] nums = new int[N + 1];
    static HashSet<Integer> set = new HashSet<>();

    static void dfs(int n) {
        if (n > N) {
            int a = nums[1];
            int b = nums[2];
            int c = nums[6];
            for (int i = 1; i < 4; ++i) b = b * 10 + nums[2 + i];
            for (int i = 1; i < 4; ++i) c = c * 10 + nums[6 + i];
            if (a * b == c) set.add(c);
            a = a * 10 + nums[2];
            b %= 1000;
            if (a * b == c) set.add(c);
            return;
        }
        for (int i = 1; i <= N; ++i) {
            if (book[i]) continue;
            book[i] = true;
            nums[n] = i;
            dfs(n + 1);
            book[i] = false;
        }
    }

    static void run() {
        dfs(1);
        int ans = 0;
        for (Integer num : set) ans += num;
        System.out.println(ans);
    }


    //method2
    //for循环判断
//    static boolean[] flag = new boolean[10];
//
//    static void go(int x) {
//        while (x != 0) {
//            flag[x % 10] = true;
//            x /= 10;
//        }
//    }
//
//    static boolean check(int a, int b, int c) {
//        for (int i = 1; i < 10; ++i) flag[i] = false;
//        go(a);
//        go(b);
//        go(c);
//        for (int i = 1; i < 10; ++i) {
//            if (!flag[i]) return false;
//        }
//        return true;
//    }
//
//    static void run() {
//        HashSet<Integer> set = new HashSet<Integer>();
//
//        for (int i = 1; i < 100; ++i) {
//            int end = 10000 / i;
//            for (int j = i <= 9 ? 1234 : 123; j < end; ++j) {
//                int c = i * j;
//                if (check(i, j, c)) {
//                    set.add(c);
//                }
//            }
//        }
//
//        int ans = 0;
//        for (Integer num : set) ans += num;
//        System.out.println(ans);
//    }

    public static void main(String[] args) {
        long startTime = System.nanoTime();
        run();
        System.out.println("\n程序运行时间：" + (System.nanoTime() - startTime) + "ns.");
    }
}
